// import { defaultEquals } from './utils'
function defaultEquals(a, b) {
  return a === b;
}
// 助手类element
class Node {
  constructor(element) {
    this.element = element;
    this.next = undefined;
  }
}

class LinkList {
  constructor(erualIsFn = defaultEquals) {
    this.count = 0
    this.erualIsFn = erualIsFn
    this.head = undefined  // 保存引用
  }
  push(element) { // 向链表尾部添加元素
    let node = new Node(element)
    if (this.head == null) {
      this.head = node
    } else {
      let current = this.head
      while (current.next != null) {
        current = current.next
      }
      current.next = node
    }
    this.count++
  }
  insert(element, index) {// 向指定位置插入元素,0就插入0，index可以===this.count，表示插入到最后
    let node = new Node(element)
    if (index >= 0 && index <= this.count) {
      if (index === 0) {
        // let current = this.head
        node.next = this.head;
        this.head = node
      } else {
        let previous = this.getElementAt(index - 1)
        let current = previous.next
        previous.next = node;
        node.next = current
      }
      this.count++
      return true
    } else {
      return false
    }
  }
  getElementAt(index) { // 通过index获取对应元素位置
    if (index >= 0 && index < this.count) {
      let current = this.head;
      for (let i = 0; i < index && current.next != null; i++) {
        current = current.next
      }
      return current
    } else {
      return undefined
    }

  }
  removeAt(index) {//删除指定index的元素
    // 检查越界值
    if (index >= 0 && index < this.count) { // {1} 
      let current = this.head; // {2} 
      // 移除第一项
      if (index === 0) { // {3} 
        this.head = current.next;
      } else {
        let previous = this.getElementAt(index - 1); // 获取指定index的上一个，将它的上一个指向他的下一个，他自身就被删除了
        let current = previous.next;
        previous.next = current.next;

      }
      this.count--; // {9} 
      return current.element;
    }
    return undefined; // {10}
  }
  indexOf(element) { // 获取指定元素的index
    let current = this.head
    for (let i = 0; i < this.count && current != null; i++) {
      if (this.erualIsFn(element, current.element)) {
        return i
      } else {
        current = current.next;
      }
    }
    return -1
  }
  remove(element) {// 删除指定元素
    let index = this.indexOf(element);
    return this.removeAt(index)
  }
  isEmpty() { // 判断是否为空
    return this.count === 0
  }
  size() {// 返回length
    return this.count
  }
  toString() {
    if (this.head == null) {
      return ''
    }
    let objectStr = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.count; i++) {
      objectStr = `${objectStr},${current.element}`
      current = current.next
    }
    return objectStr
  }
  getHead() {
    return this.head
  }
}

class DoubleNode extends Node {
  constructor(element, next, prev) {
    super(element, next)
    this.prev = prev
  }
}
class DoubleLinkList extends LinkList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn); // {5} 
    this.tail = undefined; // {6} 新增的
  }
  insert(element, index) {// 向指定位置插入元素,0就插入0，index可以===this.count，表示插入到最后
    if (index >= 0 && index <= this.count) {
      let node = new DoubleNode(element)
      let current = this.head
      if (index === 0) {// 插入首部
        if (this.head == null) {
          this.head = node;
          this.tail = node
        } else {
          node.next = current;
          current.prev = node;
          this.head = node
        }
      } else if (index === this.count) {
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = node;
        node.prev = previous;
        node.next = current;
        current.prev = node
      }
      this.count++;
      return true
    } else {
      return false
    }
  }
  removeAt(index) { // 删除指定索引的元素，index 不能等于this.count,
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        // this.count >1时，this.tail不用变，等于1需要指向undefined，所以要判断
        this.head = current.next
        if (this.count === 1) {
          this.tail = undefined
          // count ==1时，this.head此时已经为undefined，不用给this.head.prev赋值了
        } else {
          this.head.prev = undefined
        }
      } else if (index === this.count - 1) {
        current = this.tail;
        let previous = current.prev;
        previous.next = undefined
        this.tail = previous

      } else {
        let previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
        current.next.prev = previous
      }
      this.count--;
      return current.element
    }
    else {
      return undefined
    }
  }
  // 双向链表末尾添加
  push(element) {
    let node = new DoubleNode(element)
    if (this.head == null && this.tail == null) {
      this.head = node;
      this.tail = node
    } else {
      let current = this.tail;
      current.next = node;
      node.prev = current;
      this.tail = node
    }
    this.count++
  }
}
let doubleLinkList = new DoubleLinkList()
doubleLinkList.push(1)
doubleLinkList.push(2)
doubleLinkList.push(3)
doubleLinkList.push(4)
doubleLinkList.push(5)

console.log(doubleLinkList.size())
console.log(doubleLinkList.getElementAt(doubleLinkList.size() - 1))
// 单向循环列表不含this.tail
class CircleLinkList extends LinkList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn)
  }
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      let node = new DoubleNode(element)
      let current = this.head;
      if (index === 0) {
        if (this.head == null) {
          this.head = node;
          this.head.next = this.head
        } else {
          node.next = this.head
          current = this.getElementAt(this.size() - 1); // ==this.getElementAt(this.size())但是减1我觉得更符合获取索引-1就是最后一个元素
          current.next = node;
          this.head = node
        }
      } else {
        let previous = this.getElementAt(index - 1)
        current = previous.next
        node.next = current
        previous.next = node
      }
      this.count++

    } else {
      return false
    }
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        if (this.size() === 1) {
          this.head = undefined
        } else {
          let previous = this.getElementAt(this.size() - 1);
          previous.next = current.next;
          this.head = current.next
        }
      } else {
        let previous = this.getElementAt(this.count - 1);
        current = previous.next;
        previous.next = current.next
      }
      this.count--
      return current.element
    } else {
      return undefined
    }
  }
  push(element) {
    let node = new Node(element)
    if (this.count === 0) {
      this.head = node;
      this.head.next = node
    } else {
      let previous = this.getElementAt(this.count - 1)
      previous.next = node;
      node.next = this.head
    }
    this.count++
  }
}
let circleLinkList = new CircleLinkList()
circleLinkList.push(1)
circleLinkList.push(2)
circleLinkList.push(3)
circleLinkList.insert(4, 3)
circleLinkList.insert(5, 0)
console.log(circleLinkList)
// 双向循环列表


// 有序列表
